1500B - Two chandeliers - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MAXN = (int) (5e5 + 100);
const ll INF = (ll) (1e18);

vpi equivalence[2 * MAXN];
int pos[2 * MAXN];
int n, m;
ll k;
int a[MAXN], b[MAXN];
bool seen[MAXN];
int match[MAXN];

ll calc_off(int off) {
    return m - match[off];
}

ll mult(ll a, ll b) {
    if(a == 0 || b == 0) return 0;
    if(INF / a < b) return INF;
    return a * b;
}

ll add(ll a, ll b) {
    if(INF - a < b) return INF;
    return a + b;
}

void solve() {
    cin >> n >> m >> k;
    if(n < m) {
        for(int i = 0; i < n; i++) cin >> a[i];
        for(int i = 0; i < m; i++) cin >> b[i];
    }
    else {
        swap(n, m);
        for(int i = 0; i < m; i++) cin >> b[i];
        for(int i = 0; i < n; i++) cin >> a[i];
    }

    for(int i = 0; i < m; i++) pos[b[i]] = i;

    for(int i = 0; i < n; i++) {
        if(b[pos[a[i]]] == a[i]) {
            match[(i - pos[a[i]] % n + n) % n]++;
        }
    }

    vl cycle_pref;
    int off = 0;

    while(true) {
        if(seen[off]) break;
        seen[off] = true;

        ll curr = calc_off(off);
        if(!cycle_pref.empty()) curr += cycle_pref.back();
        cycle_pref.pb(curr);

        off = (off + m % n) % n;
    }

    ll cycle_size = cycle_pref.size();
    cycle_size *= m;

    ll low = 1, high = (ll) (1e18), ans = -1;
    while(low <= high) {
        ll mid = (low + high) / 2;
        ll have = mid;
        ll num_bad = 0;

        num_bad = add(num_bad, mult(have / cycle_size, cycle_pref.back()));
        have %= cycle_size;

        if(have > 0) {
            int num_full = have / m;
            if(num_full > 0) {
                num_bad = add(num_bad, cycle_pref[num_full - 1]);
                have %= m;
            }

            if(have > 0) {
                int off = 1LL * num_full * (m % n) % n;
                for(int i = 0; i < m; i++) {
                    if(have == 0) break;
                    have--;
                    if(a[(off + i) % n] != b[i]) num_bad++;
                }
            }
        }


        if(num_bad >= k) {
            ans = mid;
            high = mid - 1;
        }
        else low = mid + 1;
    }

    cout << ans << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int tc = 1;

    for(int tt = 1; tt <= tc; tt++) {
        solve();
    }

    return 0;
}